package br.ufmg.vod.wbr.algorithims.components;

import javolution.util.FastList;
import br.ufmg.vod.collections.IntQueueStack;
import br.ufmg.vod.collections.IntStack;
import br.ufmg.vod.wbr.api.Graph;

public class WeaklyConnectedComponentDFS implements Runnable {
	

	private final Graph graph;
	private boolean[] visited;
	private IntStack componentStack;
	private IntStack stack;
	
	private FastList<int[]> components;
	private int[] giantComponent;

	public WeaklyConnectedComponentDFS(Graph graph){
		this.graph = graph;
		this.visited = new boolean[graph.getNumVertex()];
		this.componentStack = new IntQueueStack(graph.getNumVertex());
		this.stack = new IntQueueStack(graph.getNumVertex());
		components = new FastList<int[]>();
	}
	
	@Override
	public void run() {
		dfsAllVertex();
	}

	public void dfsAllVertex() {
		for (int u = 0; u < this.graph.getNumVertex(); u++) {
			if( !visited[u] ){
				this.visited[u]=true;
				dfsIterative(u);
				int[] component = this.componentStack.toArray( new int[componentStack.size()] );
				this.components.add(component);
				giantComponent = giantComponent == null || giantComponent.length < component.length ? component : giantComponent;
				this.componentStack.clear();
			}
		}
	}

	public void dfsSingleVertex(int u) {
		if( !visited[u] ){
			this.visited[u]=true;
			dfsIterative(u);
//			dfsRecursive(u);
		}
	}

	private void dfsRecursive(int u) {
		int[] neighbours = graph.getEdges(u);
		for (int i = 0; i < neighbours.length; i++) {
			int v = neighbours[i];
			if( v < graph.getNumVertex() && !visited[i]  ){
				this.visited[v]=true;
				this.dfsRecursive(v);
			}
		}
		this.componentStack.push(u);
	}

	
	private void dfsIterative(int u) {
		this.visited[u]=true;
		this.stack.push(u);
		this.stack.push(-1);
		this.iterativeDfsVisit();
	}

	private void iterativeDfsVisit() {
		
		while(!stack.isEmpty()){
			recursion:{
				int i = stack.pop()+1;
				int u = stack.pop();
				int[] neighbours = graph.getEdges(u);
				for (; i < neighbours.length; i++) {
					int v = neighbours[i];
					if(!visited[v]){
						this.stack.push(u);
						this.stack.push(i);
						this.stack.push(v);
						this.stack.push(-1);
						visited[v]=true;
						break recursion;
					}
				}
				this.componentStack.push(u);
			}
		}
	}

	public Graph getGraph() {
		return graph;
	}

	public boolean[] getVisited() {
		return visited;
	}

	public IntStack getStack() {
		return componentStack;
	}

	public FastList<int[]> getComponents() {
		return components;
	}

	public void setComponents(FastList<int[]> components) {
		this.components = components;
	}

	public int[] getGiantComponent() {
		return giantComponent;
	}

	public void setGiantComponent(int[] giantComponent) {
		this.giantComponent = giantComponent;
	}

	public void setVisited(boolean[] visited) {
		this.visited = visited;
	}
	
	


}
